
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-11-11
 * Time: 16:33
 */
public class BinarySearchTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    private TreeNode root;

    /**
     * 1.找到val值，返回节点的地址
     * 时间复杂度：最好情况：O(logN)
     */
        //递归
    public TreeNode search(int val){
        if (root == null) return null;
        TreeNode cur = root;
        if (val > cur.val){
            cur = cur.right;
            return search(val);
        }else if (val < cur.val){
            cur = cur.left;
            return search(val);
        }
        return cur;
    }
        //非递归
    public TreeNode search1(int val){
        TreeNode cur = root;
        while (cur != null) {
            if (val < cur.val) cur = cur.left;
            else if (val > cur.val)cur = cur.right;
            else return cur;
        }
        return null;
    }
    /**
     * 2.插入val
     */
    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        if (root == null) {
            root = node;
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = root;
        while (cur != null){
            parent = cur;
            if (val > cur.val) {
                cur = cur.right;
            }else if (val < cur.val){
                cur = cur.left;
            }else{
                return false;
            }
        }
        if (val > parent.val) parent.right = node;
        else parent.left = node;
        return true;
    }
    /**
     * 3.删除val
     */
    public void removeNode(int val){
        TreeNode cur = root;
        while(cur != null) {
            TreeNode parent = cur;
            if (val > cur.val) cur = cur.right;
            else if (val < cur.val) cur = cur.left;
            else{
                remove(cur, parent);
                return;
            }
        }
        System.out.println("没有你要删除的数据！！！");
    }

    /**
     * 删除cur节点
     * @param cur 要被删除的节点
     * @param parent 被删节点的父节点
     */
    private void remove(TreeNode cur, TreeNode parent) {
        if (cur.left == null){
            if (cur == root){
                root = cur.right;
            }else if (cur == parent.left){
                parent.left = cur.right;
            }else{
                parent.right = cur.right;
            }
        }else if (cur.right == null){
            if (cur == root){
                root = cur.left;
            }else if (cur == parent.left){
                parent.left = cur.left;
            }else{
                parent.right = cur.left ;
            }
        }else{
            TreeNode target = cur.right;
            TreeNode targetParent = cur;
            while(target.left != null){
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if (target == targetParent.left) {
                targetParent.left = target.right;
            }else{
                targetParent.right = target.right;
            }
        }
    }
    public void inOrder(){
        inOrderSort(root);
    }
    private void inOrderSort(TreeNode root){
        if (root == null) return;
        inOrderSort(root.left);
        System.out.print(root.val + " ");
        inOrderSort(root.right);
    }
}
